// 给定一个整数数组 temperatures ，表示每天的温度，返回一个数组 answer ，其中 answer[i] 是指对于第 i 天，下一个更高温度出现在几天后。如果气温在这之后都不会升高，请在该位置用 0 来代替。

// 示例 1:

// 输入: temperatures = [73, 74, 75, 71, 69, 72, 76, 73]
// 输出: [1, 1, 4, 2, 1, 1, 0, 0]
// 示例 2:

// 输入: temperatures = [30, 40, 50, 60]
// 输出: [1, 1, 1, 0]

/**
 * @param {number[]} temperatures
 * @return {number[]}
 */
var dailyTemperatures = function (temperatures) {
    // let map = new Map();
    // const n = temperatures.length;
    // let res = new Array(n).fill(0);

    // for (let i = n - 1; i >= 0; i--) {
    //     map.set(temperatures[i], i);
    //     if (i === n - 1) { 
    //         res[i] = 0;
    //         continue;
    //     }
    //     let temp = Array.from(map).filter(value => value[0] > temperatures[i]).sort((a ,b) => a[1] - b[1]);
    //     if (temperatures[i] === temperatures[i + 1])
    //         res[i] = res[i + 1] === 0 ? 0 : res[i + 1] + 1;
    //     else
    //         res[i] = temp.length > 0? temp[0][1] - i : 0;
    // }
    // return res;

    // 单调栈实现
    const n = temperatures.length;
    let res = new Array(n).fill(0);
    let st = [];
    for (let i = 0; i < n; i++) {
        while (st.length > 0 && temperatures[i] > temperatures[st[st.length - 1]]) {
            let index = st[st.length - 1];
            res[index] = i - index;
            st.pop();
        }
        st.push(i);
    }
    return res;
};

const temperatures = [73, 74, 75, 71, 69, 72, 76, 73];
const ans = dailyTemperatures(temperatures);
console.log(ans);


